class TrailableDict(dict):
    """This class is essentially responsible for keeping a dictionary where each key has an 
    associated stack of values, thus allowing us to push new values for a key and later rollback 
    to the previous values. An individual stack is kept for each key, and a main stack groups 
    the changes applied to the individual stacks (e.g. if keys A and B are changed simultaneously,
    popping the main stack is equivalent to popping the individual stacks for A and B."""
    def __init__(self, *args, **kwargs):
        dict.__init__(self)
        self._stack = dict()
        self._main_stack = []
        if len(args) + len(kwargs) > 0:
            self.push(*args, **kwargs)
            
    def __setitem__(self, key, value):
        self.set([key, value])
        
    def __delitem__(self, key):
        self.remove(key)
        
    def set(self, *args, **kwargs):
        """Set the values for the specified keys, but instead of pushing the changes to the main 
        stack, these are added to the current frame in the main stack."""
        if len(args) > 0:
            kwargs.update(args)
        if len(self._main_stack) == 0:
            self._main_stack.append(set())
        key_set = self._main_stack[-1]
        for key, value in kwargs.iteritems():
            if key in self:
                if key in key_set:
                    self._stack[key][-1] = value
                else:
                    self._stack[key].append(value)
            else:
                self._stack[key] = [value]
            dict.__setitem__(self, key, value)
        key_set.update(kwargs.iterkeys())
        
    def push(self, *args, **kwargs):
        """Push an arbitrary number of keys into the dictionary. For each key which did not 
        exist before in the dictionary, a new stack is created and added to the main stack."""
        self._main_stack.append(set())
        self.set(*args, **kwargs)
        
    def multipop(self, *args, **kwargs):
        """Pop one or more keys from the function stack. If no keys are specified, keys 
        belonging to the top-most level of the main stack are popped. Each key to be popped
        is associated with the number of times it should be rolled back."""
        if len(args) > 0:
            kwargs.update(args)
        if len(kwargs) == 0:
            kwargs = dict((key, 1) for key in self._main_stack[-1])
        for key, n in kwargs.iteritems():
            idx = len(self._main_stack) - 1
            while idx >= 0 and n > 0:
                keys = self._main_stack[idx]
                if key in keys:
                    # remove key from the keyset in the main stack and remove the 
                    # keyset if it becomes empty from removing the key
                    if len(keys) > 1:
                        keys.remove(key)
                    else:
                        self._main_stack.pop(idx)
                    # pop the key's individual stack or eliminate the key and its  
                    # stack if the latter becomes empty from the pop operation
                    stack = self._stack[key]
                    if len(stack) > 1:
                        stack.pop()
                        dict.__setitem__(self, key, stack[-1])
                    else:
                        del self._stack[key]
                        dict.__delitem__(self, key)
                    n -= 1
                idx -= 1
            if n > 0:
                raise ValueError("unable to rollback key %s another %d times" % (key, n))
                
    def pop(self, *keys):
        """Pop one or more keys from the function stack. If no keys are specified, keys 
        belonging to the top-most level of the main stack are popped. All keys are popped 
        exactly once. For popping more than once the multipop() method should be used."""
        self.multipop(*[(key, 1) for key in keys])
        
    def remove(self, *keys):
        """Completely remove one or more keys from the dictionary."""
        assert len(keys) > 0
        self.multipop(*[(key, len(self._stack[key])) for key in keys])
        
    def clear(self):
        """Completely empty the dictionary."""
        dict.clear(self)
        self._stack = dict()
        self._main_stack = []
        